\bigskip
\bigskip
{\magonebf 5.2 Undirected graphs (ugraph)}

{\bf 1. Definition}

An instance $G$ of the data type $ugraph$ consists of a set of nodes $V$ and a 
set of undirected edges $E$. Every edge $e \in E$ is a set of two nodes 
$\{v,w\}$, $v$ and $w$ are called the endpoints of $e$. With every node $v$ is 
associated the list of its adjacent edges 
$adj\_list(v) = \{\ e \in E\ | v \in e\ \}$.

\def\name{$ugraph$}
\def\type{ugraph}

\bigskip
{\bf 2. Creation}

\create G {}

creates an instance $G$ of type $ugraph$ and initializes it to the
empty undirected graph.


\bigskip
{\bf 3. Operations }
\medskip
Most operations are the same as for directed graphs. The following operations
are either additional or have different effects.
\medskip
\+\cleartabs & \hskip 1.5truecm & \hskip 5.8truecm &\cr
\+\op node opposite {node\ v,\ edge\ e} 
                               {returns $w$ if $e = \{v,w\}$, nil otherwise}
\smallskip
\+\op int  degree {node\ v} 
                               {returns the degree of node $v$.}
\smallskip
\+\op edge new\_edge {node\ v,\ node\ w}
                             {inserts the undirected edge $\{v,w\}$ into $G$ by}
\+\nop                       {appending it to the adjacency lists of both}
\+\nop                       {$v$ and $w$ and returns it }
\smallskip
\+\op edge new\_edge {node\ v,\ node\ w,\ edge\ e1,\ edge\ e2,\ dir1=after,\ dir2=after} {}
\+\nop                {inserts the undirected edge $\{v,w\}$ after (if $dir1$}
\+\nop                {$=after$) or before (if $dir1=before$) the edge}
\+\nop                {$e1$ into the adjacency list of $v$ and after (if $dir2$}
\+\nop                {$=after$) or before (if $dir2=before$) the edge }
\+\nop                {$e2$ into the adjacency list of $w$ and returns it}
\smallskip
\+\op edge adj\_succ {edge\ e,\ node\ v} 
                             {returns the successor of edge $e$ in the}
\+\nop                       {adjacency list of $v$. }
\smallskip
\+\op edge adj\_pred {edge\ e,\ node\ v} 
                             {returns the predecessor of edge $e$ in the}
\+\nop                       {adjacency list of $v$. }
\smallskip
\+\op edge cyclic\_adj\_succ {edge\ e,\ node\ v} {}
\+\nop                       {returns the cyclic successor of edge $e$ in the}
\+\nop                       {adjacency list of $v$. }
\smallskip
\+\op edge cyclic\_adj\_pred {edge\ e,\ node\ v} {}
\+\nop                       {returns the cyclic predecessor of edge $e$ in the}
\+\nop                       {adjacency list of $v$. }


\bigskip
{\bf 4. Implementation}

Undirected graphs are implemented like directed graphs by adjacency lists. 
The adjacency list of a node $v$ contains all edges $\{v,w\}$ of the graph.
Most operations take constant time, except of all\_nodes, all\_edges, 
del\_all\_nodes, del\_all\_edges, clear, write, and read which take time 
$O(n+m)$, where $n$ is the current number of nodes and $m$ is the current 
number of edges. The space requirement is $O(n+m)$.

\vfill\eject
